'''
寻找给定的数组最多能组成多少对素数伴侣
思路：
1.  首先将输入的整数分为奇数和偶数分别存入两个列表，因为素数肯定是奇数加偶数才有可能。
2.  然后这两个列表就可以看成典型的匈牙利问题求解。遍历偶数，为每个偶数寻找奇数，
3.  当奇数偶数之和为素数且此奇数在此轮没有没选过（is_secelt[i] == 0）时，判断此奇数没有被其它偶数选择过(fi_secelt[i] == 0)，
    或选择过的那个偶数有别的奇数选择（这里就是把这个偶数再寻找一遍奇数看返回是否为真），若为真则返回True，
4.  并将记录中的奇数是否被选择的列表相应项记为对应偶数(fi_secelt[i] == odd_num)。
5.  注意在为每个偶数寻找奇数时都要初始化is_select列表。
-------------------------------------------------------------------
原文链接：https://blog.csdn.net/weixin_41480156/article/details/124125147

4
2 5 6 13
'''

# 1、判断是否是素数 (若在1到该数平方根之间都没有可除尽的数)
def isprime(num):
    if num <2: return False # 0 1 不是素数
    if num <= 3: return True
    if num % 2 == 0: return False  # 2也是素数，所以值判断大于3以上的

    for i in range(2, int(num ** 0.5) + 1): # 从2遍历到他的开平方加一就好，节约时间
        if not num % i:
            return False
    return True

# 2. 寻找偶数对应的奇数
def find_num(even, is_select, fi_select, odd_num):
    for i, e in enumerate(even):
        # 如果是素数并且该奇数没有被选择
        if isprime(e + odd_num) and is_select[i] == 0:
            is_select[i] = 1
            '''
            # is_select 记录odd_num可以匹配上的所有奇数
            # fi_select[i] == 0 如果这个奇数确实没被选择
            # find_num(even, is_select, fi_select, fi_select[i]) 如果这个奇数被选了但其匹配到的偶数有其他选择
            '''
            if fi_select[i] == 0 or find_num(even, is_select, fi_select, fi_select[i]):
                fi_select[i] = odd_num
                return True
    return False


class Solution:
    def most_prime(self, quantity, nums_list)->int:
        """
        核心思路： 素数 = 奇数 + 偶数
        中间变量： 4个
        odd = []  # 偶数列表
        even = []  # 奇数列表
        fi_select = [0] * len(even)
        is_select = [0] * len(even)
        """
        odd = []  # 偶数列表
        even = []  # 奇数列表

        if quantity == 0 or len(nums_list) == 0:
            return 0

        for i in range(quantity):  # 将输入的数分奇数和偶数存储，只有一个奇数加一个偶数的结果才可能是素数
            if nums_list[i] % 2 == 0:
                odd.append(nums_list[i])
            else:
                even.append(nums_list[i])

        result = 0
        fi_select = [0] * len(even)  # 下标对应奇数，数值为对应奇数匹配的偶数，0表示没有匹配的偶数
        for k in range(len(odd)):  # 遍历偶数，为偶数寻找奇数伴侣
            is_select = [0] * len(even)  # 记录有多少奇数能被匹配为该偶数的伴侣，0代表不是，1表示可以成为伴侣
            if find_num(even, is_select, fi_select, odd[k]):
                result = result + 1
        return result


if __name__ == '__main__':
    quantity = int(input())
    nums_list = list(map(int, input().split()))

    s = Solution()
    print(s.most_prime(quantity, nums_list))








